package com.lw.leetcode.add.e;

/**
 * Created with IntelliJ IDEA.
 * 466. 统计重复个数
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/17 17:17
 */
public class GetMaxRepetitions {

    public static void main(String[] args) {
        GetMaxRepetitions test = new GetMaxRepetitions();

        // 2
//        String str1 = "acb";
//        int n1 = 4;
//        String str2 = "ab";
//        int n2 = 2;

        // 2468 "niconiconi" 99981 "nico" 81
//        String str1 = "niconiconi";
//        int n1 = 99981;
//        String str2 = "nico";
//        int n2 = 81;

        // 4
//        String str1 = "aaa";
//        int n1 = 3;
//        String str2 = "aa";
//        int n2 = 1;

        // 4"baba"
        //11
        //"baab"
        //1
        String str1 = "baba";
        int n1 = 11;
        String str2 = "baab";
        int n2 = 1;

        // 1
//        String str1 = "acb";
//        int n1 = 1;
//        String str2 = "acb";
//        int n2 = 1;

        int maxRepetitions = test.getMaxRepetitions(str1, n1, str2, n2);
        System.out.println(maxRepetitions);
    }

    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {

        char[] as1 = s1.toCharArray();
        char[] bs1 = s2.toCharArray();
        int l1 = s1.length();
        int l2 = s2.length();
        char c = as1[0];
        boolean f = false;
        for (char c1 : as1) {
            if (c1 != c) {
                f = true;
                break;
            }
        }
        if (!f) {
            for (char c1 : bs1) {
                if (c1 != c) {
                    f = true;
                    break;
                }
            }
        }
        if (!f) {
            return l1 * n1 / (l2 * n2);
        }
        char[] as2 = new char[l1];
        for (int i = 0; i < l1; i++) {
            as2[i] = as1[l1 - i - 1];
        }
        char[] bs2 = new char[l2];
        for (int i = 0; i < l2; i++) {
            bs2[i] = bs1[l2 - i - 1];
        }


        long v1 = find(as1, bs1);
        int end = (int) (v1 >> 32);
        int count = (int) v1;
        if (count != 0) {
            long v2 = find(as2, bs2);
            int end2 = (int) (l1 - 1 - (v2 >> 32));
            if (end2 < end) {
                return n1 / count / n2;
            } else {
                if (count  < 2) {
                    return 0;
                }
                return (n1 - 1) / (count - 1) / n2;
            }
        }  else {
            v1 = find2(as1, bs1);
            end = (int) (v1 >> 32);
            count = (int) v1;
            if (count != 0) {
                long v2 = find2(as2, bs2);
                int end2 = (int) (l1 - 1 - (v2 >> 32));
                if (end2 < end) {
                    return n1 * count / n2;
                } else {
                    return  (n1 + 1) * (count + 1) / n2;
                }
            }
        }
        return 0;

    }

    private long find(char[] arr1, char[] arr2) {
        int a = arr1.length;
        int b = arr2.length;
        int i = 0;
        int j = 0;
        int c = 1;
        while (j != b) {
            if (i == a) {
                c++;
                i = 0;
            }
            if (arr2[j] == arr1[i]) {
                i++;
                j++;
            } else {
                i++;
            }
        }
        if (c == 1 && i < a) {
            return 0;
        }
//        if (i != a) {
//            c--;
//        }
        return ((i - 1L) << 32) + c;
    }


    private long find2(char[] arr1, char[] arr2) {

        int a = arr1.length;
        int b = arr2.length;

        int i = 0;
        int j = 0;
        int c = 1;
        long f = 0;
        while (i != a) {
            if (j == b) {
                c++;
                j = 0;
            }
            if (arr2[j] == arr1[i]) {
                i++;
                j++;
                f = i;
            } else {
                j++;
            }
        }
        if (c == 0 && j < b) {
            return 0;
        }

//        if (j != b) {
//            c--;
//        }
        return ((f) << 32) + c;
    }

}
